# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/14 17:31
功能描述:

题目背景：
在构建学术知识图谱时，一个常见的任务是找出两位作者之间的最短合作路径（类似于“六度分隔”理论）。
例如，作者A与B合作过，B与C合作过，那么A到C的路径长度为2。在一个庞大的作者网络中，这个搜索过程可能非常耗时。你可以通过并行化来加速搜索过程。

任务描述：
给定一个学者合作网络（用邻接表字典表示）和一个起始学者、一个目标学者，你需要找到他们之间的最短合作路径长度。在实现广度优先搜索（BFS）时，你需要对“扩展当前层节点（即查找当前层所有学者的合作者）”这一步进行并行化处理，以模拟在真实大数据场景下的加速效果。

"""
import collections #  # 用于实现队列数据结构，BFS的核心组件
from concurrent.futures import ThreadPoolExecutor # 用于实现并行处理
from typing import Dict, List, Optional ## 用于类型提示，提高代码可读性和可维护性

#定义协作网络的数据类型：键为学者姓名，值为该学者的合作者列表
#这里的 Dict 本质上对应 Python 自带的内置类型 dict，但它来自 typing 模块，是用于类型提示（Type Hints） 的泛型类型标记。
#Dict[str, List[str]] 是一个类型注解，表示 “键为 str 类型、值为 List[str] 类型（字符串列表）的字典”。
# 这里的 Dict 并非重新定义了一个新的字典类型，而是告诉开发者和工具（如 IDE）：CollaborationGraph 这个类型别名对应的是 Python 内置的 dict，但有明确的键值类型约束（键是字符串，值是字符串列表）。
#这种写法的目的是增强代码的可读性和类型检查能力，不影响字典的实际功能（运行时仍然是普通的 dict 对象）
CollaborationGraph = Dict[str, List[str]]


def get_collaborators(graph: CollaborationGraph, author: str) -> List[str]:
    """
        获取指定学者的所有合作者
        参数:
            graph: 学者合作网络（邻接表）
            author: 要查询的学者姓名
        返回:
            该学者的合作者列表，如果学者不在网络中则返回空列表
        """
    import time
    #模拟网络延迟或计算耗时，实际场景中可能是从数据库或API获取数据
    time.sleep(0.01)
    return graph.get(author, [])


#Optional[int] 是 Python typing 模块中的类型提示，它表示返回值可以是 int 类型，或者是 None（等价于 Union[int, None]）。
def parallel_bfs_shortest_path(graph: CollaborationGraph, start_author: str, end_author: str) -> Optional[int]:
    """
        使用并行化BFS查找两位学者之间的最短合作路径长度
        参数:
            graph: 学者合作网络（邻接表）
            start_author: 起始学者姓名
            end_author: 目标学者姓名
        返回:
            最短路径长度，如果不存在路径或输入无效则返回None
        """
    #检查起始或目标学者是否不在合作网络中，若不在则返回None
    #本题的潜在意思是：只要是作者，都会有自己的键值对的合作关系的体现
    if start_author not in graph or end_author not in graph:
        return None
    ## 如果起始学者就是目标学者，直接返回路径长度0
    if start_author == end_author:
        return 0
    #初始化BFS队列，存储元组(学者姓名, 距离)，从起始学者开始，初始距离为0
    #collections.deque 是 Python 标准库提供的双端队列数据结构，支持高效的两端元素添加 / 删除操作（时间复杂度 O (1)）
    #在 BFS 中，队列用于按层次顺序存储待处理的节点，确保先处理距离起始点更近的节点（符合 “广度优先” 的特性）
    #初始状态下，队列中只有起始学者这一个元素，因为 BFS 需要从起点开始逐层扩散。
    #这行代码通过双端队列初始化了 BFS 的起点和初始距离，是整个广度优先搜索的 “启动开关”，确保算法从起始学者开始按层次有序扩散。
    queue = collections.deque([(start_author, 0)])
    #记录已访问过的学者，避免重复访问和循环路径
    visited = {start_author}
    #创建线程池，最多使用4个线程进行并行处理
    with ThreadPoolExecutor(max_workers=4) as executor:
        #BFS主循环，队列不为空时持续处理
        while queue:
            # 获取当前BFS层的所有节点
            level_size = len(queue)
            current_level_nodes = []
            ## 从队列中取出当前层的所有节点
            for _ in range(level_size):
                #queue.popleft() 是从双端队列（deque）的左侧（头部）移除并返回第一个元素的操作
                #为什么用dequeue的popleft() 而不是普通列表的 pop(0)？
                # deque.popleft() 是高效操作，时间复杂度为 O (1)（无论队列大小，耗时固定）；
                # 而如果用普通列表的 pop(0)，时间复杂度为 O (n)（需要移动列表中所有元素）。
                # 由于 BFS 中需要频繁从队列头部取元素，使用 deque.popleft() 能显著提升效率，尤其在处理大规模网络（节点多）时差距明显。
                author, dist = queue.popleft()
                # 如果当前节点是目标学者，返回当前距离（找到最短路径）
                if author == end_author:
                    return dist
                current_level_nodes.append(author)  # 函数参数列表（当前层的所有学者）
            # 使用executor.map
            # map的结果顺序与输入顺序一致
            next_level_neighbors_lists = executor.map(
                lambda author: get_collaborators(graph, author), # 要并行执行的函数
                current_level_nodes)  # 函数参数列表（当前层的所有学者）
            # 计算下一层节点的距离（当前层距离+1）
            # 如果队列不为空，取队列中第一个元素的距离（当前层处理前的距离）；否则用当前层距离
            dist = queue[0][1] if queue else dist  # 获取上一轮的距离
            for neighbors in next_level_neighbors_lists:
                for neighbor in neighbors:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, dist + 1))
                        # 找到目标就可以提前返回，但为了完成本层并行，这里简化为下一轮检查
                        # 在循环开头检查更快
    return None  # 如果循环结束仍未找到目标学者，说明不存在路径，返回None


# ---- 测试代码 ----
# 定义一个示例学术合作网络（邻接表表示）
academic_graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C', 'F'],
    'C': ['B', 'E', 'G'],
    'D': ['A', 'E'],
    'E': ['C', 'D'],
    'F': ['B'],
    'G': ['C', 'H'],
    'H': ['G']
}

#测试用例列表：(起始学者, 目标学者)
# FB GC和文档答案不一致，文档中答案是 2 2
test_cases = [('A', 'A'), ('A', 'C'), ('A', 'G'), ('F', 'B'), ('E', 'D'), ('H', 'A'), ('A', 'X'), ('G', 'C'),
              ('B', 'H'), ('D', 'F')]

for start, end in test_cases:
    path_len = parallel_bfs_shortest_path(academic_graph, start, end)
    print(f"{path_len}")


"""
补充1：Python 的普通列表（list）没有 popleft() 方法。
普通列表中与 “移除元素” 相关的方法是：
pop(index)：移除并返回指定索引位置的元素（默认移除最后一个元素，即 pop() 等价于 pop(-1)）。
如果要移除列表的第一个元素，需要用 pop(0)，但这个操作效率较低（时间复杂度为 O (n)，因为需要将列表中所有后续元素向前移动一位）。
对比：
列表（list）：无 popleft()，移除第一个元素用 pop(0)（效率低）。
双端队列（collections.deque）：有 popleft() 方法，移除第一个元素的效率极高（时间复杂度 O (1)），适合频繁从头部操作元素的场景（如 BFS）。

"""